﻿//////////////////////////////////////////////////////////////////
//
// TerrainHolder.cs
//
// Copyright (c) 2012 Dan Pike.
//
// Permission is hereby granted, free of charge, to any person
// obtaining a copy of this software and associated documentation files
// (the "Software"), to deal in the Software without restriction,
// including without limitation the rights to use, copy, modify, merge,
// publish, distribute, sublicense, and/or sell copies of the Software,
// and to permit persons to whom the Software is furnished to do so,
// subject to the following conditions:
//
// The above copyright notice and this permission notice shall be included
// in all copies or substantial portions of the Software.
//
// THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND, EXPRESS
// OR IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF
// MERCHANTABILITY, FITNESS FOR A PARTICULAR PURPOSE AND NONINFRINGEMENT.
// IN NO EVENT SHALL THE AUTHORS OR COPYRIGHT HOLDERS BE LIABLE FOR ANY
// CLAIM, DAMAGES OR OTHER LIABILITY, WHETHER IN AN ACTION OF CONTRACT,
// TORT OR OTHERWISE, ARISING FROM, OUT OF OR IN CONNECTION WITH THE
// SOFTWARE OR THE USE OR OTHER DEALINGS IN THE SOFTWARE.
//
using Interfaces;
using Microsoft.Xna.Framework.Graphics;
using System;
using System.Collections.Generic;
using System.Linq;
using System.Text;
using Utilities;
using Microsoft.Xna.Framework;

using Point = System.Drawing.Point;

namespace WindowXna
{
   /// <summary>
   /// Holds information relating to the vertices that make up the terrain,
   /// such as the vertices, a bounding box that helps in detecting collisions
   /// when doing mouse-picking
   /// </summary>
   internal class TerrainHolder
   {
      ////////////////////////////////////////////////////////////////////////

      private static Logger logger_;
      private GraphicsDevice graphicsDevice_;
      private VertexPositionColorNormal[] vertexData_;
      private VertexBuffer vertexBuffer_;
      private BoundingBox[,] boundingBoxes_;
      private ushort[] indices_;
      private IndexBuffer indexBuffer_;
      private short offsetX_;
      private short offsetY_;
      private DateTime lastUsedAt_;

      // These are not normals for shading, as they do not match up directly to
      // the triangle strip. They are the plane normals as calculated using the
      // convention that V0 is the vertex at the right-angled corner, and that
      // the normal is equal to (V1 - V0) x (V2 - V0)
      private Vector3[] pickerNormals_;

      ////////////////////////////////////////////////////////////////////////
      /// <summary>
      /// 
      /// </summary>
      public TerrainHolder()
      {
         logger_ = Program.Logger;
      }

      ////////////////////////////////////////////////////////////////////////
      /// <summary>
      /// 
      /// </summary>
      public override string ToString()
      {
         return string.Format("[offsetX={0}, offsetY={1}]", OffsetX, OffsetY);
      }

      ////////////////////////////////////////////////////////////////////////
      /// <summary>
      /// 
      /// </summary>
      public VertexBuffer VertexBuffer
      {
         set { vertexBuffer_ = value; }
         get
         {
            if (null == vertexBuffer_)
            {
               // Initialize the bounding boxes
               boundingBoxes_ = new BoundingBox[Const.boxCount10, Const.boxCount10];
               for (int boxY = 0; boxY < Const.boxCount10; ++boxY)
               {
                  for (int boxX = 0; boxX < Const.boxCount10; ++boxX)
                  {
                     float minZ = float.MaxValue, maxZ = float.MinValue;
                     for (int vertexY = 0; vertexY <= Const.cellsPerBox; ++vertexY)
                     {
                        for (int vertexX = 0; vertexX <= Const.cellsPerBox; ++vertexX)
                        {
                           int vertexIndex = (boxY * Const.cellsPerBox + vertexY) * Const.tileWidth61 + (boxX * Const.cellsPerBox + vertexX);
                           float height = vertexData_[vertexIndex].Position.Z;
                           minZ = Math.Min(minZ, height);
                           maxZ = Math.Max(maxZ, height);
                        }
                     }

                     boundingBoxes_[boxX, boxY].Min = new Vector3((boxX + OffsetX * Const.boxCount10) * Const.cellsPerBox,
                        (boxY + OffsetY * Const.boxCount10) * Const.cellsPerBox, minZ);
                     boundingBoxes_[boxX, boxY].Max = new Vector3((boxX + OffsetX * Const.boxCount10 + 1) * Const.cellsPerBox,
                        (boxY + OffsetY * Const.boxCount10 + 1) * Const.cellsPerBox, maxZ);
                  }
               }

               // Rebuild the normals, as something has changed
               RefreshNormals();

               // And create a new VertexBuffer to match
               vertexBuffer_ = new VertexBuffer(GraphicsDevice, VertexPositionColorNormal.VertexDeclaration,
                  vertexData_.Length, BufferUsage.None);
               vertexBuffer_.SetData(vertexData_, 0, vertexData_.Length);
            }
            return vertexBuffer_;
         }
      }

      ////////////////////////////////////////////////////////////////////////
      /// <summary>
      /// The index buffer that should be used with this vertex buffer (initially
      /// there is only one index buffer in the system but we may change it later
      /// to have smaller buffers)
      /// </summary>
      public IndexBuffer IndexBuffer
      {
         get { return indexBuffer_; }
      }

      ////////////////////////////////////////////////////////////////////////
      /// <summary>
      /// 
      /// </summary>
      public GraphicsDevice GraphicsDevice
      {
         get { return graphicsDevice_; }
         set { graphicsDevice_ = value; }
      }

      ////////////////////////////////////////////////////////////////////////
      /// <summary>
      /// 
      /// </summary>
      public short OffsetX
      {
         get { return offsetX_; }
         set { offsetX_ = value; }
      }

      ////////////////////////////////////////////////////////////////////////
      /// <summary>
      /// 
      /// </summary>
      public short OffsetY
      {
         get { return offsetY_; }
         set { offsetY_ = value; }
      }

      ////////////////////////////////////////////////////////////////////////
      /// <summary>
      /// 
      /// </summary>
      public DateTime LastUsedAt
      {
         get { return lastUsedAt_; }
         set { lastUsedAt_ = value; }
      }

      ////////////////////////////////////////////////////////////////////////
      /// <summary>
      /// 
      /// </summary>
      /// <param name="vertexData"></param>
      public VertexPositionColorNormal[] VertexData
      {
         get { return vertexData_; }
         set
         {
            vertexData_ = value;

            // Force a refresh
            vertexBuffer_ = null;
         }
      }

      ////////////////////////////////////////////////////////////////////////
      /// <summary>
      /// 
      /// </summary>
      private void RefreshNormals()
      {
         try
         {
            // Intermediate calculations for hit-tests and things
            Vector3 v0, v1, v2;
            Vector3[] vertices = new Vector3[3];
            pickerNormals_ = new Vector3[indices_.Length - 2];

            // The first two vertices prime the triangle strip
            int index = 0;
            int[] currentIndices = new int[3];

            currentIndices[0] = indices_[0];
            currentIndices[1] = indices_[1];
            vertices[0] = vertexData_[currentIndices[0]].Position;
            vertices[1] = vertexData_[currentIndices[1]].Position;

            // Then we go along calculating all of the normals to the
            // triangles for the mouse-picking
            indices_.Skip(2).All(thisIndex =>
               {
                  try
                  {
                     // complete the next triangle to calculate
                     currentIndices[2] = thisIndex;
                     vertices[2] = VertexData[currentIndices[2]].Position;

                     // Work out which of the vertices is the hinge (V0) and which
                     // are the two sides V1 and V2
                     Vector3 normal = Vector3.Zero;
                     if (AlignVertices(out v0, out v1, out v2, vertices))
                     {
                        // Calculate the normal of this triangle by crossing the two sides
                        // with vertex #0 being the hinge point.
                        normal = Vector3.Cross(v1 - v0, v2 - v0);
                        if (0 > normal.Z)
                        {
                           // We want the normal pointing upwards. The triangle strip
                           // paints alternating clockwise/anti-clockwise triangles
                           normal = -normal;
                        }

                        // If it's not a degenerate triangle, store the normal
                        if ((Vector3.Zero != normal) && !float.IsNaN(normal.LengthSquared()))
                        {
                           // Add all the adjacent normals on the triangle vertices so that
                           // we can average them
                           for (int visitor = 0; visitor < 3; ++visitor)
                           {
                              vertexData_[currentIndices[visitor]].Normal += normal;
                           }

                           // Store the whole-triangle normal for mouse-picking
                           normal.Normalize();
                           pickerNormals_[index] = normal;
                        }
                     }

                     // Shift along to the next triangle
                     currentIndices[0] = currentIndices[1];
                     currentIndices[1] = currentIndices[2];
                     vertices[0] = vertices[1];
                     vertices[1] = vertices[2];
                     ++index;
                  }
                  catch (System.Exception ex)
                  {
                     logger_.Exception("calculating normal #{0}", ex, index);
                  }
                  return true;
               });

            // Now we can average all of the triangle normals that we totalled up on our way
            // through the triangle strips
            for (int vertexIndex = 0; vertexIndex < vertexData_.Length; ++vertexIndex)
            {
               if (Vector3.Zero == vertexData_[vertexIndex].Normal)
               {
                  vertexData_[vertexIndex].Normal = Vector3.UnitZ;
               }
               else
               {
                  vertexData_[vertexIndex].Normal.Normalize();
               }
            }
         }
         catch (System.Exception ex)
         {
            logger_.Exception(ex);
         }
      }

      ////////////////////////////////////////////////////////////////////////
      /// <summary>
      /// 
      /// </summary>
      /// <param name="v0"></param>
      /// <param name="v1"></param>
      /// <param name="v2"></param>
      /// <param name="v"></param>
      private bool AlignVertices(out Vector3 v0, out Vector3 v1, out Vector3 v2, Vector3[] v)
      {
         // There are three sorts of triangles in the strip. The first has the horizontal section
         // at the bottom, the second has it at the top and the third is zero-width and is used
         // at each end to change direction cleanly (without having to start a new strip)
         //
         // These three types may be presented with the vertices in any order
         if (v[0].Y == v[1].Y)
         {
            if (v[0].X == v[2].X)
            {
               v0 = v[0];     // v[2] +         or  v[1] +-+ v[0]
               v1 = v[1];     //      |\                  \|
               v2 = v[2];     // v[0] +-+ v[1]             + v[2]
               return true;
            }
            if (v[1].X == v[2].X)
            {
               v0 = v[1];     // v[2] +         or  v[0] +-+ v[1]
               v1 = v[0];     //      |\                  \|
               v2 = v[2];     // v[1] +-+ v[0]             + v[2]
               return true;
            }
         }
         else if (v[1].Y == v[2].Y)
         {
            if (v[0].X == v[2].X)
            {
               v0 = v[2];     // v[0] +         or  v[1] +-+ v[2]
               v1 = v[1];     //      |\                  \|
               v2 = v[0];     // v[2] +-+ v[1]             + v[0]
               return true;
            }
            if (v[0].X == v[1].X)
            {
               v0 = v[1];     // v[0] +         or  v[2] +-+ v[1]
               v1 = v[2];     //      |\                  \|
               v2 = v[0];     // v[1] +-+ v[2]             + v[0]
               return true;
            }
         }
         else if (v[0].Y == v[2].Y)
         {
            if (v[1].X == v[2].X)
            {
               v0 = v[2];     // v[1] +        or  v[0] +-+ v[2]
               v1 = v[0];     //      |\                 \|  
               v2 = v[1];     // v[2] +-+ v[0]            + v[1]
               return true;
            }
            if (v[0].X == v[1].X)
            {
               v0 = v[0];     // v[1] +        or  v[2] +-+ v[0]
               v1 = v[2];     //      |\                 \|  
               v2 = v[1];     // v[0] +-+ v[2]            + v[1]
               return true;
            }
         }
         // degenerate
         v0 = v1 = v2 = Vector3.Zero;
         return false;
      }

      ////////////////////////////////////////////////////////////////////////
      /// <summary>
      /// 
      /// </summary>
      /// <param name="indices"></param>
      public KeyValuePair<ushort[], IndexBuffer> Indices
      {
         get
         {
            return new KeyValuePair<ushort[],IndexBuffer>(indices_, indexBuffer_);
         }
         set
         {
            indices_ = value.Key;
            indexBuffer_ = value.Value;

            // Force a refresh
            vertexBuffer_ = null;
         }
      }

      ////////////////////////////////////////////////////////////////////////
      /// <summary>
      /// This algorithm is taken from:
      ///   http://www.softsurfer.com/Archive/algorithm_0105/algorithm_0105.htm
      /// which is also saved in Dependencies/TriangleRayIntersection/*
      /// </summary>
      /// <param name="ray"></param>
      /// <param name="v0"></param>
      /// <param name="v1"></param>
      /// <param name="v2"></param>
      /// <param name="normal"></param>
      /// <param name="s"></param>
      /// <param name="t"></param>
      /// <returns></returns>
      private bool CalculateIntersection(Ray ray, Vector3 v0, Vector3 v1,
         Vector3 v2, Vector3 normal, out float s, out float t)
      {
         float a = -Vector3.Dot(normal, ray.Position - v0);
         float b = Vector3.Dot(normal, ray.Direction);

         // Ignore degenerate case, e.g. ray is parallel to this triangle
         if (float.IsNaN(a) || float.IsNaN(b) || (1.0e-6 > Math.Abs(b)))
         {
            s = t = float.NaN;
            return false;
         }
         // Get point at which the ray intersects with the triangle
         float r = a / b;
         if (0.0f > r)
         {
            // The ray points away from the triangle (it is behind us)
            s = t = float.NaN;
            return false;
         }

         // Intersection point of ray and plane of this triangle
         Vector3 I = ray.Position + r * ray.Direction;

         Vector3 u = v1 - v0;
         Vector3 v = v2 - v0;

         // Is the intersection point inside the triangle?
         float uu = Vector3.Dot(u, u);
         float uv = Vector3.Dot(u, v);
         float vv = Vector3.Dot(v, v);
         Vector3 w = I - v0;
         float wu = Vector3.Dot(w, u);
         float wv = Vector3.Dot(w, v);
         float denom = uv * uv - uu * vv;

         // Finally, we calculate the parametric coordinates
         s = (uv * wv - vv * wu) / denom;
         t = (uv * wu - uu * wv) / denom;

         // Return true if they lie within the triangle
         return (0.0 <= s) && (1.0f >= s) && (0.0 <= t) && (1.0f >= (s + t));
      }

      ////////////////////////////////////////////////////////////////////////
      /// <summary>
      /// Find a list of the bounding boxes that intersect this ray
      /// </summary>
      private bool FindIntersection(List<Tuple<int, int>> boxes, Ray ray)
      {
         for (int boxY = 0; boxY < Const.boxCount10; ++boxY)
         {
            for (int boxX = 0; boxX < Const.boxCount10; ++boxX)
            {
               if (null != ray.Intersects(boundingBoxes_[boxX, boxY]))
               {
                  boxes.Add(new Tuple<int, int>(boxX, boxY));
               }
            }
         }
         return 0 < boxes.Count;
      }

      ////////////////////////////////////////////////////////////////////////
      /// <summary>
      ///
      /// </summary>
      /// <param name="hits"></param>
      /// <param name="ray"></param>
      /// <param name="startX"></param>
      /// <param name="startY"></param>
      /// <returns></returns>
      public void FindIntersection(List<Vector3?> hits, Ray ray, int startX, int startY)
      {
         Vector3[] vertices = new Vector3[3];
         Vector3 v0, v1, v2;

         // Check each of the rows in the given bounding box
         int index = 0, direction = 0;
         for (int row = startY; row < startY + Const.cellsPerBox; ++row)
         {
            // Offset into the IndexBuffer of the first vertex in this row
            // of the bounding box. This depends on the direction in which
            // we are traversing the cells
            if (0 == (row % 2))
            {
               index = 2 * (row * Const.tileWidth61 + startX);
               direction = 1;
            }
            else
            {
               index = 2 * (row * Const.tileWidth61 + Const.tileWidth61 - startX - 1);
               direction = -1;
            }

            // Prime the search
            vertices[0] = vertexData_[indices_[index]].Position;
            index += direction;
            vertices[1] = vertexData_[indices_[index]].Position;
            for (int column = 0; column < 2 * Const.cellsPerBox; ++column)
            {
               index += direction;
               vertices[2] = vertexData_[indices_[index]].Position;

               // Work out which of the vertices is the hinge (V0) and which
               // are the two sides V1 and V2
               Vector3 normal = pickerNormals_[index - 2];
               if ((Vector3.Zero != normal) && AlignVertices(out v0, out v1, out v2, vertices))
               {
                  float s, t;
                  if (CalculateIntersection(ray, v0, v1, v2, normal, out s, out t))
                  {
                     // Remember the cell position that holds this triangle
                     // This is the lower-left corner of the enclosing box
                     hits.Add(new Vector3(
                        Math.Min(Math.Min(v0.X, v1.X), v2.X),
                        Math.Min(Math.Min(v0.Y, v1.Y), v2.Y),
                        (v0.Z + v1.Z + v2.Z) / 3.0f));
                  }

                  // Get the next triangle to match
                  vertices[0] = vertices[1];
                  vertices[1] = vertices[2];
               }
            }
         }
      }

      ////////////////////////////////////////////////////////////////////////
      /// <summary>
      /// Find a triangle that intersects this ray.
      /// </summary>
      /// <param name="ray"></param>
      /// <returns></returns>
      public Vector3? FindIntersection(Ray ray)
      {
         try
         {
            if (null == pickerNormals_)
            {
               // There is no planet displayed
               return null;
            }

            List<Tuple<int, int>> boxes = new List<Tuple<int, int>>();
            if (!FindIntersection(boxes, ray))
            {
               // The ray does not intersect with any of the bounding boxes
               // enclosing this tile, so it won't intersect any of the
               // triangles inside them
               //logger_.debugFormat("ray {0} did not intersect any bounding box", ray);
               return null;
            }
            //logger_.debugFormat("ray intersects {1} bounding box(es) from {0}:",
            //   ray, boxes.Count);
            //boxes.ForEach(box => logger_.debugFormat("...box=[{0}, {1}]",
            //   box.Item1 + offsetX, box.Item2 + offsetY));

            // Check all of the triangles in the bounding boxes
            // that intersected the ray. (There are many fewer of these
            // to check than there would have been if we were to check the
            // whole tile.)
            List<Vector3?> hits = new List<Vector3?>();
            boxes.ForEach(boxIndex => FindIntersection(hits, ray,
               boxIndex.Item1 * Const.cellsPerBox,
               boxIndex.Item2 * Const.cellsPerBox));

            // Choose the "closest" hit.
            // For testing, just assume that there's only one
            return (0 < hits.Count) ? hits[0] : null;
         }
         catch (System.Exception ex)
         {
            logger_.Exception(ex);
         }
         return null;
      }
   }
}
